斐波那契
/* 斐波那契数列：递归 */
function fib(n: number): number {
    // 终止条件 f(1) = 0, f(2) = 1
    if (n === 1 || n === 2) return n - 1;
    // 递归调用 f(n) = f(n-1) + f(n-2)
    const res = fib(n - 1) + fib(n - 2);
    // 返回结果 f(n)
    return res;
}

// 一个链表 ListNode节点
class ListNode {
  val: number;
  next: ListNode | null;
 
  constructor(val?: number, next?: ListNode | null) {
    this.val = val || 0;
    this.next = next || null;
  }
}
 
// 一个双向链表Class (具备前后指针)
class ListNodeS {
  val: number;
  next: ListNodeS | null;
  pre: ListNodeS | null;
 
  constructor(val?: number, next?: ListNodeS | null, pre?: ListNodeS | null) {
    this.val = val || 0;
    this.next = next || null;
    this.pre = pre || null;
  }
}
 
const run = () => {
  // 创建一个list 1 -> 3 -> 2 -> 5 -> 4 */
  const n0 = new ListNode(1);
  const n1 = new ListNode(3);
  const n2 = new ListNode(2);
  const n3 = new ListNode(5);
  const n4 = new ListNode(4);
 
  n0.next = n1;
  n1.next = n2;
  n2.next = n3;
  n3.next = n4;
  console.log(n0);
 
  // 插入一个节点 就是改变其指针 (在n0 后插入 p)
  const insert = (n0: ListNode, P: ListNode): void => {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
  };
 
  // 删除 就是吧某个指针设置为null
  const remove = (n0: ListNode): void => {
    if (!n0.next) return;
 
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
  };
 
  // 访问索引 为index的节点
  const access = (head: ListNode | null, index: number): ListNode | null => {
    for (let i = 0; i < index; i++) {
      if (!head) return null;
      head = head.next;
    }
    return head;
  };
 
  // 查找某个元素
  const find = (head: ListNode | null, target: number): number => {
    let idx = 0;
    while (head != null) {
      if (head.val === target) {
        return idx;
      }
      head = head.next;
      idx += 1;
    }
    return -1;
  };
 
  console.log('find--->', find(n0, 4));
};
 
export { run };
 
 

/* 双向链表节点类 */
class ListNode {
    val: number;
    next: ListNode | null;
    prev: ListNode | null;
    constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
        this.val = val  ===  undefined ? 0 : val;        // 节点值
        this.next = next  ===  undefined ? null : next;  // 指向后继节点的引用
        this.prev = prev  ===  undefined ? null : prev;  // 指向前驱节点的引用
    }
}

/* 列表类 */
class MyList {
    private arr: Array<number>; // 数组（存储列表元素）
    private _capacity: number = 10; // 列表容量
    private _size: number = 0; // 列表长度（当前元素数量）
    private extendRatio: number = 2; // 每次列表扩容的倍数
 
    /* 构造方法 */
    constructor() {
        this.arr = new Array(this._capacity);
    }
 
    /* 获取列表长度（当前元素数量）*/
    public size(): number {
        return this._size;
    }
 
    /* 获取列表容量 */
    public capacity(): number {
        return this._capacity;
    }
 
    /* 访问元素 */
    public get(index: number): number {
        // 索引如果越界，则抛出异常，下同
        if (index < 0 || index >= this._size) throw new Error('索引越界');
        return this.arr[index];
    }
 
    /* 更新元素 */
    public set(index: number, num: number): void {
        if (index < 0 || index >= this._size) throw new Error('索引越界');
        this.arr[index] = num;
    }
 
    /* 在尾部添加元素 */
    public add(num: number): void {
        // 如果长度等于容量，则需要扩容
        if (this._size === this._capacity) this.extendCapacity();
        // 将新元素添加到列表尾部
        this.arr[this._size] = num;
        this._size++;
    }
 
    /* 在中间插入元素 */
    public insert(index: number, num: number): void {
        if (index < 0 || index >= this._size) throw new Error('索引越界');
        // 元素数量超出容量时，触发扩容机制
        if (this._size === this._capacity) {
            this.extendCapacity();
        }
        // 将索引 index 以及之后的元素都向后移动一位
        for (let j = this._size - 1; j >= index; j--) {
            this.arr[j + 1] = this.arr[j];
        }
        // 更新元素数量
        this.arr[index] = num;
        this._size++;
    }
 
    /* 删除元素 */
    public remove(index: number): number {
        if (index < 0 || index >= this._size) throw new Error('索引越界');
        let num = this.arr[index];
        // 将索引 index 之后的元素都向前移动一位
        for (let j = index; j < this._size - 1; j++) {
            this.arr[j] = this.arr[j + 1];
        }
        // 更新元素数量
        this._size--;
        // 返回被删除的元素
        return num;
    }
 
    /* 列表扩容 */
    public extendCapacity(): void {
        // 新建一个长度为 size 的数组，并将原数组复制到新数组
        this.arr = this.arr.concat(
            new Array(this.capacity() * (this.extendRatio - 1))
        );
        // 更新列表容量
        this._capacity = this.arr.length;
    }
 
    /* 将列表转换为数组 */
    public toArray(): number[] {
        let size = this.size();
        // 仅转换有效长度范围内的列表元素
        const arr = new Array(size);
        for (let i = 0; i < size; i++) {
            arr[i] = this.get(i);
        }
        return arr;
    }
}

 
class LinkedListStatck {
  private stackPeek: ListNode | null; // 栈顶
  private stkSize: number = 0;
 
  constructor() {
    this.stackPeek = null;
  }
 
  get size(): number {
    return this.stkSize;
  }
 
  isEmpty(): boolean {
    return this.size === 0;
  }
 
  push(val: number): void {
    const node = new ListNode(val);
    node.next = this.stackPeek;
    this.stackPeek = node; // 环形
    this.stkSize++;
  }
 
  pop(): number {
    const val = this.peek();
    this.stackPeek = this.stackPeek.next;
    this.stkSize--;
    return val;
  }
 
  // 访问栈顶
  peek(): number {
    return this.stackPeek.val;
  }
 
  // 转Arry
  toArray(): Array<number> {
    let node = this.stackPeek;
    const res = new Array<number>(this.size);
    for (let i = res.length - 1; i >= 0; i--) {
      res[i] = node.val;
      node = node.next;
    }
    return res;
  }
}
 

 
// 基于Array的实现 这个就非常的简单了 Arrry本身就具备Stack的部分特征
class ArrayStack {
  private stack: Array<number>;
 
  constructor() {
    this.stack = [];
  }
 
  get size(): number {
    return this.stack.length;
  }
 
  isEmpyt() {
    return this.stack.length === 0;
  }
 
  push(val: number) {
    this.stack.push(val);
  }
 
  pop() {
    this.stack.pop();
  }
 
  peek() {
    return this.stack[this.stack.length - 1];
  }
 
  toArray() {
    return this.stack;
  }
}
 

// 基于链表实现的queue
class LinkedListQueue {
  private front: ListNode|null; // 头尾节点
  private rear:ListNode|null; 
  private queSize:number=0;
 
  constructor(){
    this.front = null;
    this.rear = null;
  }
 
  get size(){
    return this.size;
  }
 
  isEmpty(){
    return this.size === 0;
  }
 
  push(val:number){
    const node = new ListNode(val);
    // 如果为空
    if(!this.front){
      this.front = node;
      this.rear=node;
    }else{
      this.rear!.next = node;
      this.rear = node;
    }
    // 否则
    this.queSize++
  }
 
  pop(){
    const val = this.peek();
 
    // 直接移动指针
    this.front = this.front.next;
    this.queSize--
 
    return val;
  }
 
  peek(){
    return this.front!.val
  }
 
  toArrray(){
    let node = this.front
    const res = new Array(this.size)
    for( let i = 0; i< res.length; i++ ){
      res[i] = node.val;
      node = node.next;
    }
    return res
  }
 
}
 

 
这里为什么要做复杂设计呢？主要是由于Array的删除首元素的时间复杂度是O(n), 我们要想办法优化它
 
/* 基于环形数组实现的队列 */
class ArrayQueue {
    private nums: number[]; // 用于存储队列元素的数组
    private front: number; // 队首指针，指向队首元素
    private queSize: number; // 队列长度
 
    constructor(capacity: number) {
        this.nums = new Array(capacity);
        this.front = this.queSize = 0;
    }
 
    /* 获取队列的容量 */
    get capacity(): number {
        return this.nums.length;
    }
 
    /* 获取队列的长度 */
    get size(): number {
        return this.queSize;
    }
 
    /* 判断队列是否为空 */
    isEmpty(): boolean {
        return this.queSize === 0;
    }
 
    /* 入队 */
    push(num: number): void {
        if (this.size === this.capacity) {
            console.log('队列已满');
            return;
        }
        // 计算队尾指针，指向队尾索引 + 1
        // 通过取余操作实现 rear 越过数组尾部后回到头部
        const rear = (this.front + this.queSize) % this.capacity;
        // 将 num 添加至队尾
        this.nums[rear] = num;
        this.queSize++;
    }
 
    /* 出队 */
    pop(): number {
        const num = this.peek();
        // 队首指针向后移动一位，若越过尾部，则返回到数组头部
        this.front = (this.front + 1) % this.capacity;
        this.queSize--;
        return num;
    }
 
    /* 访问队首元素 */
    peek(): number {
        if (this.isEmpty()) throw new Error('队列为空');
        return this.nums[this.front];
    }
 
    /* 返回 Array */
    toArray(): number[] {
        // 仅转换有效长度范围内的列表元素
        const arr = new Array(this.size);
        for (let i = 0, j = this.front; i < this.size; i++, j++) {
            arr[i] = this.nums[j % this.capacity];
        }
        return arr;
    }
}

const deque  = []
 
// 入队
deque.push(2)
deque.push(5)
deque.push(4)
deque.unshift(3) // 注意这个方法的时间复杂度为 O(n)
 
// 获取
deque[0]
deque[deque.length-1]
 
// 出队 shift 的时间复杂为 O(n)
const popFront = deque.shift()
const popBack = deque.pop()
 

class ListNodeV2 {
  pre: ListNodeV2;
  next: ListNodeV2;
  val: number;
  constructor(val: number) {
    this.val = val;
    this.pre = null;
    this.next = null;
  }
}
 
class LinkedListDeque {
  private front: ListNodeV2; // 头和尾节点
  private rear: ListNodeV2;
  private queSize: number;
 
  constructor() {
    this.front = null;
    this.rear = null;
    this.queSize = 0;
  }
 
  // push 的两个方向
  pushLast(val: number) {
    const node = new ListNodeV2(val);
    if (this.queSize === 0) {
      this.front = node;
      this.rear = node;
    } else {
      // 注意环操作！
      this.rear.next = node;
      node.pre = this.rear;
      this.rear = node;
    }
    this.queSize++;
  }
 
  pushFirst(val: number) {
    const node = new ListNodeV2(val);
    if (this.queSize == 0) {
      this.front = node;
      this.rear = node;
    } else {
      this.front.pre = node;
      node.next = this.front;
      this.front = node;
    }
 
    this.queSize++;
  }
 
  // pop的两个方向
  popLast() {
    const value = this.rear.val;
 
    let temp = this.rear.pre;
    if (temp) {
      temp.next = null;
      this.rear.pre = null;
    }
 
    // 尾处理
    this.rear = temp;
    this.queSize--;
    return value;
  }
 
  popFirts() {
    const value = this.front.val;
 
    let temp = this.front.next;
    if (temp) {
      temp.next = null;
      this.front.next = null;
    }
 
    // 尾处理
    this.front = temp;
    this.queSize--;
    return value;
  }
}

/* 基于环形数组实现的双向队列 */
class ArrayDeque {
    private nums: number[]; // 用于存储双向队列元素的数组
    private front: number; // 队首指针，指向队首元素
    private queSize: number; // 双向队列长度
 
    /* 构造方法 */
    constructor(capacity: number) {
        this.nums = new Array(capacity);
        this.front = 0;
        this.queSize = 0;
    }
 
    /* 获取双向队列的容量 */
    capacity(): number {
        return this.nums.length;
    }
 
    /* 获取双向队列的长度 */
    size(): number {
        return this.queSize;
    }
 
    /* 判断双向队列是否为空 */
    isEmpty(): boolean {
        return this.queSize === 0;
    }
 
    /* 计算环形数组索引 */
    index(i: number): number {
        // 通过取余操作实现数组首尾相连
        // 当 i 越过数组尾部后，回到头部
        // 当 i 越过数组头部后，回到尾部
        return (i + this.capacity()) % this.capacity();
    }
 
    /* 队首入队 */
    pushFirst(num: number): void {
        if (this.queSize === this.capacity()) {
            console.log('双向队列已满');
            return;
        }
        // 队首指针向左移动一位
        // 通过取余操作实现 front 越过数组头部后回到尾部
        this.front = this.index(this.front - 1);
        // 将 num 添加至队首
        this.nums[this.front] = num;
        this.queSize++;
    }
 
    /* 队尾入队 */
    pushLast(num: number): void {
        if (this.queSize === this.capacity()) {
            console.log('双向队列已满');
            return;
        }
        // 计算队尾指针，指向队尾索引 + 1
        const rear: number = this.index(this.front + this.queSize);
        // 将 num 添加至队尾
        this.nums[rear] = num;
        this.queSize++;
    }
 
    /* 队首出队 */
    popFirst(): number {
        const num: number = this.peekFirst();
        // 队首指针向后移动一位
        this.front = this.index(this.front + 1);
        this.queSize--;
        return num;
    }
 
    /* 队尾出队 */
    popLast(): number {
        const num: number = this.peekLast();
        this.queSize--;
        return num;
    }
 
    /* 访问队首元素 */
    peekFirst(): number {
        if (this.isEmpty()) throw new Error('The Deque Is Empty.');
        return this.nums[this.front];
    }
 
    /* 访问队尾元素 */
    peekLast(): number {
        if (this.isEmpty()) throw new Error('The Deque Is Empty.');
        // 计算尾元素索引
        const last = this.index(this.front + this.queSize - 1);
        return this.nums[last];
    }
 
    /* 返回数组用于打印 */
    toArray(): number[] {
        // 仅转换有效长度范围内的列表元素
        const res: number[] = [];
        for (let i = 0, j = this.front; i < this.queSize; i++, j++) {
            res[i] = this.nums[this.index(j)];
        }
        return res;
    }
}

const index = hash(key) % capacity

// 对所有的number -> string
 
class Pair {
  public key: number;
  public val: number;
  constructor(key: number, val: string){
    this.key = key;
    this.val = val;
  }
}
 
// 基于Array的实现
class ArrayHashMap {
	private readyonly buckets:(Pari|null)[];
 
  constructor(){
    this.buckets = new Array(100).fill(null);
  }
 
  private hasFunc(key: number):number{
    return key % 100;
  }
    /* 查询操作 */
    public get(key: number): string | null {
        let index = this.hashFunc(key);
        let pair = this.buckets[index];
        if (pair === null) return null;
        return pair.val;
    }
 
    /* 添加操作 */
    public set(key: number, val: string) {
        let index = this.hashFunc(key);
        this.buckets[index] = new Pair(key, val);
    }
 
    /* 删除操作 */
    public delete(key: number) {
        let index = this.hashFunc(key);
        // 置为 null ，代表删除
        this.buckets[index] = null;
    }
  public entries(){
    let arr;
 
    for( let i = 0; i < this.buckets.length; i++ ){
      if(this.bukest[i]){
        arr.push(this.this.bukest[i])
      }
    }
    return arr;
  } 
  
 	public keys(): (number | undefined)[] {
    let arr: (number | undefined)[] = [];
    for (let i = 0; i < this.buckets.length; i++) {
        if (this.buckets[i]) {
            arr.push(this.buckets[i].key);
        }
    }
    return arr;
}
  
  public values() {
    let arr: (string)[] = [];
    for( let i = 0; i < this.buckets.length; i++ ){
      if(this.buckets[i]) {
        arr.push( this.buckets[i].val );
      }
      return arr;
    }
  }
 
  public print(){
    let pairSet = this.entries();
    for( const pair of pairSet ) {
      console.log(`${pair.key} -> ${pair.value}`)
    }
  }
  
}

class Pair {
  public key: number;
  public val: number;
  constructor(key: number, val: string){
    this.key = key;
    this.val = val;
  }
}
 
 
/* 链式地址哈希表 */
class HashMapChaining {
    #size: number; // 键值对数量
    #capacity: number; // 哈希表容量
    #loadThres: number; // 触发扩容的负载因子阈值
    #extendRatio: number; // 扩容倍数
    #buckets: Pair[][]; // 桶数组
 
    /* 构造方法 */
    constructor() {
        this.#size = 0;
        this.#capacity = 4;
        this.#loadThres = 2.0 / 3.0;
        this.#extendRatio = 2;
        this.#buckets = new Array(this.#capacity).fill(null).map((x) => []);
    }
 
    /* 哈希函数 */
    #hashFunc(key: number): number {
        return key % this.#capacity;
    }
 
    /* 负载因子 */
    #loadFactor(): number {
        return this.#size / this.#capacity;
    }
 
    /* 查询操作 */
    get(key: number): string | null {
        const index = this.#hashFunc(key);
        const bucket = this.#buckets[index];
        // 遍历桶，若找到 key ，则返回对应 val
        for (const pair of bucket) {
            if (pair.key === key) {
                return pair.val;
            }
        }
        // 若未找到 key ，则返回 null
        return null;
    }
 
    /* 添加操作 */
    put(key: number, val: string): void {
        // 当负载因子超过阈值时，执行扩容
        if (this.#loadFactor() > this.#loadThres) {
            this.#extend();
        }
        const index = this.#hashFunc(key);
        const bucket = this.#buckets[index];
        // 遍历桶，若遇到指定 key ，则更新对应 val 并返回
        for (const pair of bucket) {
            if (pair.key === key) {
                pair.val = val;
                return;
            }
        }
        // 若无该 key ，则将键值对添加至尾部
        const pair = new Pair(key, val);
        bucket.push(pair);
        this.#size++;
    }
 
    /* 删除操作 */
    remove(key: number): void {
        const index = this.#hashFunc(key);
        let bucket = this.#buckets[index];
        // 遍历桶，从中删除键值对
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket.splice(i, 1);
                this.#size--;
                break;
            }
        }
    }
 
    /* 扩容哈希表 */
    #extend(): void {
        // 暂存原哈希表
        const bucketsTmp = this.#buckets;
        // 初始化扩容后的新哈希表
        this.#capacity *= this.#extendRatio;
        this.#buckets = new Array(this.#capacity).fill(null).map((x) => []);
        this.#size = 0;
        // 将键值对从原哈希表搬运至新哈希表
        for (const bucket of bucketsTmp) {
            for (const pair of bucket) {
                this.put(pair.key, pair.val);
            }
        }
    }
 
    /* 打印哈希表 */
    print(): void {
        for (const bucket of this.#buckets) {
            let res = [];
            for (const pair of bucket) {
                res.push(pair.key + ' -> ' + pair.val);
            }
            console.log(res);
        }
    }
}

/* 开放寻址哈希表 */
class HashMapOpenAddressing {
    private size: number; // 键值对数量
    private capacity: number; // 哈希表容量
    private loadThres: number; // 触发扩容的负载因子阈值
    private extendRatio: number; // 扩容倍数
    private buckets: Array<Pair | null>; // 桶数组
    private TOMBSTONE: Pair; // 删除标记
 
    /* 构造方法 */
    constructor() {
        this.size = 0; // 键值对数量
        this.capacity = 4; // 哈希表容量
        this.loadThres = 2.0 / 3.0; // 触发扩容的负载因子阈值
        this.extendRatio = 2; // 扩容倍数
        this.buckets = Array(this.capacity).fill(null); // 桶数组
        this.TOMBSTONE = new Pair(-1, '-1'); // 删除标记
    }
 
    /* 哈希函数 */
    private hashFunc(key: number): number {
        return key % this.capacity;
    }
 
    /* 负载因子 */
    private loadFactor(): number {
        return this.size / this.capacity;
    }
 
    /* 搜索 key 对应的桶索引 */
    private findBucket(key: number): number {
        let index = this.hashFunc(key);
        let firstTombstone = -1;
        // 线性探测，当遇到空桶时跳出
        while (this.buckets[index] !== null) {
            // 若遇到 key ，返回对应的桶索引
            if (this.buckets[index]!.key === key) {
                // 若之前遇到了删除标记，则将键值对移动至该索引处
                if (firstTombstone !== -1) {
                    this.buckets[firstTombstone] = this.buckets[index];
                    this.buckets[index] = this.TOMBSTONE;
                    return firstTombstone; // 返回移动后的桶索引
                }
                return index; // 返回桶索引
            }
            // 记录遇到的首个删除标记
            if (
                firstTombstone === -1 &&
                this.buckets[index] === this.TOMBSTONE
            ) {
                firstTombstone = index;
            }
            // 计算桶索引，越过尾部则返回头部
            index = (index + 1) % this.capacity;
        }
        // 若 key 不存在，则返回添加点的索引
        return firstTombstone === -1 ? index : firstTombstone;
    }
 
    /* 查询操作 */
    get(key: number): string | null {
        // 搜索 key 对应的桶索引
        const index = this.findBucket(key);
        // 若找到键值对，则返回对应 val
        if (
            this.buckets[index] !== null &&
            this.buckets[index] !== this.TOMBSTONE
        ) {
            return this.buckets[index]!.val;
        }
        // 若键值对不存在，则返回 null
        return null;
    }
 
    /* 添加操作 */
    put(key: number, val: string): void {
        // 当负载因子超过阈值时，执行扩容
        if (this.loadFactor() > this.loadThres) {
            this.extend();
        }
        // 搜索 key 对应的桶索引
        const index = this.findBucket(key);
        // 若找到键值对，则覆盖 val 并返回
        if (
            this.buckets[index] !== null &&
            this.buckets[index] !== this.TOMBSTONE
        ) {
            this.buckets[index]!.val = val;
            return;
        }
        // 若键值对不存在，则添加该键值对
        this.buckets[index] = new Pair(key, val);
        this.size++;
    }
 
    /* 删除操作 */
    remove(key: number): void {
        // 搜索 key 对应的桶索引
        const index = this.findBucket(key);
        // 若找到键值对，则用删除标记覆盖它
        if (
            this.buckets[index] !== null &&
            this.buckets[index] !== this.TOMBSTONE
        ) {
            this.buckets[index] = this.TOMBSTONE;
            this.size--;
        }
    }
 
    /* 扩容哈希表 */
    private extend(): void {
        // 暂存原哈希表
        const bucketsTmp = this.buckets;
        // 初始化扩容后的新哈希表
        this.capacity *= this.extendRatio;
        this.buckets = Array(this.capacity).fill(null);
        this.size = 0;
        // 将键值对从原哈希表搬运至新哈希表
        for (const pair of bucketsTmp) {
            if (pair !== null && pair !== this.TOMBSTONE) {
                this.put(pair.key, pair.val);
            }
        }
    }
 
    /* 打印哈希表 */
    print(): void {
        for (const pair of this.buckets) {
            if (pair === null) {
                console.log('null');
            } else if (pair === this.TOMBSTONE) {
                console.log('TOMBSTONE');
            } else {
                console.log(pair.key + ' -> ' + pair.val);
            }
        }
    }
}

 
/* 加法哈希 */
function addHash(key: string): number {
    let hash = 0;
    const MODULUS = 1000000007;
    for (const c of key) {
        hash = (hash + c.charCodeAt(0)) % MODULUS;
    }
    return hash;
}
 
/* 乘法哈希 */
function mulHash(key: string): number {
    let hash = 0;
    const MODULUS = 1000000007;
    for (const c of key) {
        hash = (31 * hash + c.charCodeAt(0)) % MODULUS;
    }
    return hash;
}
 
/* 异或哈希 */
function xorHash(key: string): number {
    let hash = 0;
    const MODULUS = 1000000007;
    for (const c of key) {
        hash ^= c.charCodeAt(0);
    }
    return hash & MODULUS;
}
 
/* 旋转哈希 */
function rotHash(key: string): number {
    let hash = 0;
    const MODULUS = 1000000007;
    for (const c of key) {
        hash = ((hash << 4) ^ (hash >> 28) ^ c.charCodeAt(0)) % MODULUS;
    }
    return hash;
}

 
class TreeNode {
  val: number;
  left: TreeNode|null;
  right: TreeNode|null;
 
  constructor(val:number, left:TreeNode, right:TreeNode ){
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// 初始化 节点
let n1 = new TreeNode(1);
let n2 = new TreeNode(2);
let n3 = new TreeNode(3);
let n4 = new TreeNode(4);
let n5 = new TreeNode(5);
 
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
 
// 删除节点
const P = new TreeNode(0);
// n1 ->  n2 插入P
n1.left = P;
P.left = n2;
 
// 删除节点p
n1.left = n2;
 

// 广度优先遍历
function levelOrder( root: TreeNode|null ):number[] {
  const queue = [root]
  const list = [];
 
  while( queue.length ){
    let node = queue.shift();
    if(node.left){
      queue.push(node.left)
    }
    
    if(node.right){
      queue.push(node.right)
    }
  }
 
  return list
}

// 深度优先 核心实现依旧是 递归， 有三种方式 区别在于 先到底的是 左 中 右,
 
let list = []
// 前序
function preOrder(root: TreeNode | null){
  if(root === null) return;
 
  // 跟 -> 左 -> 右
  list.push(root.val)
  preOrder(root.left)
  preOrder(root.right)
}
 
// 中序
function inOrder(root: TreeNode | null){
  if(root === null) return;
 
  // 左 -> 跟 -> 右
  inOrder(root.left)
  list.push(root.val)
  inOrder(root.right)
}
 
// 后序
function postOrder(root: TreeNode | null){
  if(root === null) return;
 
  // 左 -> 右 -> 根
  postOrder(root.left)
  postOrder(root.right)
  list.push(root.val)
}

/* 二叉树的数组表示 */
// 使用 null 来表示空位
let tree: (number | null)[] = 
  [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];

 
// 基于数组的数据
/* 数组表示下的二叉树类 */
class ArrayBinaryTree {
  #tree: (number | null)[];
 
  /* 构造方法 */
  constructor(arr: (number | null)[]) {
    this.#tree = arr;
  }
 
  /* 列表容量 */
  size(): number {
    return this.#tree.length;
  }
 
  /* 获取索引为 i 节点的值 */
  val(i: number): number | null {
    // 若索引越界，则返回 null ，代表空位
    if (i < 0 || i >= this.size()) return null;
    return this.#tree[i];
  }
 
  /* 获取索引为 i 节点的左子节点的索引 */
  left(i: number): number {
    return 2 * i + 1;
  }
 
  /* 获取索引为 i 节点的右子节点的索引 */
  right(i: number): number {
    return 2 * i + 2;
  }
 
  /* 获取索引为 i 节点的父节点的索引 */
  parent(i: number): number {
    return Math.floor((i - 1) / 2); // 向下整除
  }
 
  /* 层序遍历 */
  levelOrder(): number[] {
    let res = [];
    // 直接遍历数组
    for (let i = 0; i < this.size(); i++) {
      if (this.val(i) !== null) res.push(this.val(i));
    }
    return res;
  }
 
  // 深度优先遍历 有三种方式  
  /* 深度优先遍历 */
  #dfs(i: number, order: string, res: (number | null)[]): void {
    // 若为空位，则返回
    if (this.val(i) === null) return;
    // 前序遍历
    if (order === 'pre') {
      res.push(this.val(i));
    }
    this.#dfs(this.left(i), order, res);
    // 中序遍历
    if (order === 'in') {
      res.push(this.val(i));
    }
    this.#dfs(this.right(i), order, res);
    // 后序遍历
    if (order === 'post') {
      res.push(this.val(i));
    }
  }
 
  /* 前序遍历 */
  preOrder(): (number | null)[] {
    const res = [];
    this.#dfs(0, 'pre', res);
    return res;
  }
 
  /* 中序遍历 */
  inOrder(): (number | null)[] {
    const res = [];
    this.#dfs(0, 'in', res);
    return res;
  }
 
  /* 后序遍历 */
  postOrder(): (number | null)[] {
    const res = [];
    this.#dfs(0, 'post', res);
    return res;
  }
}
 

 
/* 二叉搜索树 */
class BinarySearchTree {
    private root: TreeNode | null;
 
    /* 构造方法 */
    constructor() {
        // 初始化空树
        this.root = null;
    }
 
    /* 获取二叉树根节点 */
    getRoot(): TreeNode | null {
        return this.root;
    }
 
    /* 查找节点 */
    search(num: number): TreeNode | null {
        let cur = this.root;
        // 循环查找，越过叶节点后跳出
        while (cur !== null) {
            // 目标节点在 cur 的右子树中
            if (cur.val < num) cur = cur.right;
            // 目标节点在 cur 的左子树中
            else if (cur.val > num) cur = cur.left;
            // 找到目标节点，跳出循环
            else break;
        }
        // 返回目标节点
        return cur;
    }
 
    /* 插入节点 */
    insert(num: number): void {
        // 若树为空，则初始化根节点
        if (this.root === null) {
            this.root = new TreeNode(num);
            return;
        }
        let cur: TreeNode | null = this.root,
            pre: TreeNode | null = null;
        // 循环查找，越过叶节点后跳出
        while (cur !== null) {
            // 找到重复节点，直接返回
            if (cur.val === num) return;
            pre = cur;
            // 插入位置在 cur 的右子树中
            if (cur.val < num) cur = cur.right;
            // 插入位置在 cur 的左子树中
            else cur = cur.left;
        }
        // 插入节点
        const node = new TreeNode(num);
        if (pre!.val < num) pre!.right = node;
        else pre!.left = node;
    }
 
    /* 删除节点 */
    remove(num: number): void {
        // 若树为空，直接提前返回
        if (this.root === null) return;
        let cur: TreeNode | null = this.root,
            pre: TreeNode | null = null;
        // 循环查找，越过叶节点后跳出
        while (cur !== null) {
            // 找到待删除节点，跳出循环
            if (cur.val === num) break;
            pre = cur;
            // 待删除节点在 cur 的右子树中
            if (cur.val < num) cur = cur.right;
            // 待删除节点在 cur 的左子树中
            else cur = cur.left;
        }
        // 若无待删除节点，则直接返回
        if (cur === null) return;
        // 子节点数量 = 0 or 1
        if (cur.left === null || cur.right === null) {
            // 当子节点数量 = 0 / 1 时， child = null / 该子节点
            const child: TreeNode | null =
                cur.left !== null ? cur.left : cur.right;
            // 删除节点 cur
            if (cur !== this.root) {
                if (pre!.left === cur) pre!.left = child;
                else pre!.right = child;
            } else {
                // 若删除节点为根节点，则重新指定根节点
                this.root = child;
            }
        }
        // 子节点数量 = 2
        else {
            // 获取中序遍历中 cur 的下一个节点
            let tmp: TreeNode | null = cur.right;
            while (tmp!.left !== null) {
                tmp = tmp!.left;
            }
            // 递归删除节点 tmp
            this.remove(tmp!.val);
            // 用 tmp 覆盖 cur
            cur.val = tmp!.val;
        }
    }
}
 
/* Driver Code */
/* 初始化二叉搜索树 */
const bst = new BinarySearchTree();
// 请注意，不同的插入顺序会生成不同的二叉树，该序列可以生成一个完美二叉树
const nums = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15];
for (const num of nums) {
    bst.insert(num);
}
console.log('\n初始化的二叉树为\n');
printTree(bst.getRoot());
 
/* 查找节点 */
const node = bst.search(7);
console.log(
    '\n查找到的节点对象为 ' + node + '，节点值 = ' + (node ? node.val : 'null')
);
 
/* 插入节点 */
bst.insert(16);
console.log('\n插入节点 16 后，二叉树为\n');
printTree(bst.getRoot());
 
/* 删除节点 */
bst.remove(1);
console.log('\n删除节点 1 后，二叉树为\n');
printTree(bst.getRoot());
bst.remove(2);
console.log('\n删除节点 2 后，二叉树为\n');
printTree(bst.getRoot());
bst.remove(4);
console.log('\n删除节点 4 后，二叉树为\n');
printTree(bst.getRoot());
 
export {};

/* AVL 树节点类 */
class TreeNode {
    val; // 节点值
    height; //节点高度
    left; // 左子节点指针
    right; // 右子节点指针
    constructor(val, left, right, height) {
        this.val = val === undefined ? 0 : val;
        this.height = height === undefined ? 0 : height;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
 
  /* 获取节点高度 */
  height(node) {
      // 空节点高度为 -1 ，叶节点高度为 0
      return node === null ? -1 : node.height;
  }
  
  /* 更新节点高度 */
  #updateHeight(node) {
      // 节点高度等于最高子树高度 + 1
      node.height =
          Math.max(this.height(node.left), this.height(node.right)) + 1;
  }
 
  // 节点的「平衡因子 balance factor」定义为节点左子树的高度减去右子树的高度
  /* 获取平衡因子 */
  balanceFactor(node) {
      // 空节点平衡因子为 0
      if (node === null) return 0;
      // 节点平衡因子 = 左子树高度 - 右子树高度
      return this.height(node.left) - this.height(node.right);
  }
 
  // 下面是左右旋转的过程
  /* 右旋操作 */
  #rightRotate(node) {
      const child = node.left;
      const grandChild = child.right;
      // 以 child 为原点，将 node 向右旋转
      child.right = node;
      node.left = grandChild;
      // 更新节点高度
      this.#updateHeight(node);
      this.#updateHeight(child);
      // 返回旋转后子树的根节点
      return child;
  }
 
  /* 左旋操作 */
  #leftRotate(node) {
      const child = node.right;
      const grandChild = child.left;
      // 以 child 为原点，将 node 向左旋转
      child.left = node;
      node.right = grandChild;
      // 更新节点高度
      this.#updateHeight(node);
      this.#updateHeight(child);
      // 返回旋转后子树的根节点
      return child;
  }
 
  /* 执行旋转操作，使该子树重新恢复平衡 */
  #rotate(node) {
      // 获取节点 node 的平衡因子
      const balanceFactor = this.balanceFactor(node);
      // 左偏树
      if (balanceFactor > 1) {
          if (this.balanceFactor(node.left) >= 0) {
              // 右旋
              return this.#rightRotate(node);
          } else {
              // 先左旋后右旋
              node.left = this.#leftRotate(node.left);
              return this.#rightRotate(node);
          }
      }
      // 右偏树
      if (balanceFactor < -1) {
          if (this.balanceFactor(node.right) <= 0) {
              // 左旋
              return this.#leftRotate(node);
          } else {
              // 先右旋后左旋
              node.right = this.#rightRotate(node.right);
              return this.#leftRotate(node);
          }
      }
      // 平衡树，无须旋转，直接返回
      return node;
  }
 
  // 接下来是它的插入操作
  /* 插入节点 */
  insert(val) {
      this.root = this.#insertHelper(this.root, val);
  }
  
  /* 递归插入节点（辅助方法） */
  #insertHelper(node, val) {
      if (node === null) return new TreeNode(val);
      /* 1. 查找插入位置并插入节点 */
      if (val < node.val) node.left = this.#insertHelper(node.left, val);
      else if (val > node.val)
          node.right = this.#insertHelper(node.right, val);
      else return node; // 重复节点不插入，直接返回
      this.#updateHeight(node); // 更新节点高度
      /* 2. 执行旋转操作，使该子树重新恢复平衡 */
      node = this.#rotate(node);
      // 返回子树的根节点
      return node;
  }
  
  // 然后是它的删除节点操作
  /* 删除节点 */
  remove(val) {
      this.root = this.#removeHelper(this.root, val);
  }
  
  /* 递归删除节点（辅助方法） */
  #removeHelper(node, val) {
      if (node === null) return null;
      /* 1. 查找节点并删除 */
      if (val < node.val) node.left = this.#removeHelper(node.left, val);
      else if (val > node.val)
          node.right = this.#removeHelper(node.right, val);
      else {
          if (node.left === null || node.right === null) {
              const child = node.left !== null ? node.left : node.right;
              // 子节点数量 = 0 ，直接删除 node 并返回
              if (child === null) return null;
              // 子节点数量 = 1 ，直接删除 node
              else node = child;
          } else {
              // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
              let temp = node.right;
              while (temp.left !== null) {
                  temp = temp.left;
              }
              node.right = this.#removeHelper(node.right, temp.val);
              node.val = temp.val;
          }
      }
      this.#updateHeight(node); // 更新节点高度
      /* 2. 执行旋转操作，使该子树重新恢复平衡 */
      node = this.#rotate(node);
      // 返回子树的根节点
      return node;
  }
}
 
 

 
/* 最大堆类 */
class MaxHeap {
    private maxHeap: number[];
    constructor(nums?: number[]) {
    }
 
    /* 获取左子节点的索引 */
    private left(i: number): number {
        return 2 * i + 1;
    }
 
    /* 获取右子节点的索引 */
    private right(i: number): number {
        return 2 * i + 2;
    }
 
    /* 获取父节点的索引 */
    private parent(i: number): number {
        return Math.floor((i - 1) / 2); // 向下整除
    }
 
    /* 交换元素 */
    private swap(i: number, j: number): void {
        const tmp = this.maxHeap[i];
        this.maxHeap[i] = this.maxHeap[j];
        this.maxHeap[j] = tmp;
    }
 
    /* 获取堆大小 */
    public size(): number {
        return this.maxHeap.length;
    }
 
    /* 判断堆是否为空 */
    public isEmpty(): boolean {
        return this.size() === 0;
    }
 
    /* 访问堆顶元素 */
    public peek(): number {
        return this.maxHeap[0];
    }
 
    /* 元素入堆 */
    public push(val: number): void {
        // 添加节点
        this.maxHeap.push(val);
        // 从底至顶堆化
        this.siftUp(this.size() - 1);
    }
 
    /* 从节点 i 开始，从底至顶堆化 */
    private siftUp(i: number): void {
        while (true) {
            // 获取节点 i 的父节点
            const p = this.parent(i);
            // 当“越过根节点”或“节点无须修复”时，结束堆化
            if (p < 0 || this.maxHeap[i] <= this.maxHeap[p]) break;
            // 交换两节点
            this.swap(i, p);
            // 循环向上堆化
            i = p;
        }
    }
 
    /* 元素出堆 */
    public pop(): number {
        // 判空处理
        if (this.isEmpty()) throw new RangeError('Heap is empty.');
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        this.swap(0, this.size() - 1);
        // 删除节点
        const val = this.maxHeap.pop();
        // 从顶至底堆化
        this.siftDown(0);
        // 返回堆顶元素
        return val;
    }
 
    /* 从节点 i 开始，从顶至底堆化 */
    private siftDown(i: number): void {
        while (true) {
            // 判断节点 i, l, r 中值最大的节点，记为 ma
            const l = this.left(i),
                r = this.right(i);
            let ma = i;
            if (l < this.size() && this.maxHeap[l] > this.maxHeap[ma]) ma = l;
            if (r < this.size() && this.maxHeap[r] > this.maxHeap[ma]) ma = r;
            // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
            if (ma === i) break;
            // 交换两节点
            this.swap(i, ma);
            // 循环向下堆化
            i = ma;
        }
    }
 
    /* 打印堆（二叉树） */
    public print(): void {
        printHeap(this.maxHeap);
    }
 
    /* 取出堆中元素 */
    public getMaxHeap(): number[] {
        return this.maxHeap;
    }
}
 
/* Driver Code */
if (require.main === module) {
    /* 初始化大顶堆 */
    const maxHeap = new MaxHeap([9, 8, 6, 6, 7, 5, 2, 1, 4, 3, 6, 2]);
    console.log('\n输入列表并建堆后');
    maxHeap.print();
 
    /* 获取堆顶元素 */
    let peek = maxHeap.peek();
    console.log(`\n堆顶元素为 ${peek}`);
 
    /* 元素入堆 */
    const val = 7;
    maxHeap.push(val);
    console.log(`\n元素 ${val} 入堆后`);
    maxHeap.print();
 
    /* 堆顶元素出堆 */
    peek = maxHeap.pop();
    console.log(`\n堆顶元素 ${peek} 出堆后`);
    maxHeap.print();
 
    /* 获取堆大小 */
    const size = maxHeap.size();
    console.log(`\n堆元素数量为 ${size}`);
 
    /* 判断堆是否为空 */
    const isEmpty = maxHeap.isEmpty();
    console.log(`\n堆是否为空 ${isEmpty}`);
}